#include <cstdio>
#include <cmath>
#include <queue>
using namespace std;
const int MAXN=10000;
int n,go[MAXN];
bool isPrime[MAXN];
struct node{
	int num,step;
};
queue <node> q;
void getPrime()
{
	for (int i=2;i<MAXN;i++)
		isPrime[i]=true;
	for (int i=2;i<=sqrt(MAXN);i++)
		if (isPrime[i]==true)
			for (int j=2;j<=MAXN/i;j++)
				isPrime[i*j]=false;
}
void bfs(int a,int b)
{
	node start;
	start.num=a;
	start.step=0;
	q.push(start);
	while (!q.empty())
	{
		node head;
		head=q.front();
		q.pop();
		if (head.num==b)
		{
			printf("%d\n",head.step);
			return;
		}
		for (int i=0;i<=9;i++)
			for (int j=1;j<=4;j++)
			{
				int now=0;
				switch (j)
				{
					case 1 : now=head.num/10*10+i;
							 break;
					case 2 : now=head.num/100*100+i*10+head.num%10;
							 break;
					case 3 : now=head.num/1000*1000+i*100+head.num%100;
							 break;
					case 4 : now=head.num%1000+i*1000;
							 break;
				}
				if (!(1000<=now&&now<=9999))
					continue;
				if (isPrime[now]==true&&go[now]==true)
				{
					go[now]=false;
					node temp;
					temp.num=now;
					temp.step=head.step+1;
					q.push(temp);
				}
			}
	}
}
int main()
{
	getPrime();
	scanf("%d",&n);
	for (int i=1;i<=n;i++)
	{
		int a,b;
		for (int i=1000;i<=9999;i++)
			go[i]=true;
		while (!q.empty())
			q.pop();
		scanf("%d%d",&a,&b);
		go[a]=false;
		bfs(a,b);
	}
}
//http://47.104.154.247/problem.php?cid=1080&pid=2 
